#include <stdio.h>

void swap(int &a, int &b) {
    int tmp = a;
    a = b;
    b = a;
}


// 快排代码默写版
void Qsort(int A[], int L, int R) {
    if (L >= R) return;         // 若排序区间内元素个数小于1，则退出
    int i = L, j = R;           // i和j是数组的两个游标
    // 数组待排序区间内随机一个数与A[L]交换位置       // 优化快排
    int key = A[L];             // key作为枢值参与比较
    while (i < j) {
        while (i<j && A[j]>key)
            j--;
        while (i<j && A[i]<=key)
            i++;
        if (i<j)
            swap(A[i], A[j]);   // 交换A[i]和A[j]的位置
    }
    A[i] = key;                 // 确定枢值的位置
    Qsort(A, L, i-1);           // 递归处理左区间
    Qsort(A, i+1, R);           // 递归处理右区间
    return;
}

/**
 * Test
 *
 * @return
 */
int main() {
//    printf("hello world");

    int A[10] = {9,8,7,5,4,3,2,1,0,6};

    Qsort(A, 0, 9);

    for (int i = 0; i < 10; ++i) {
        printf("%3d", A[i]);
    }


    return 0;
}